//https://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5?tpId=13&&tqId=11179&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking
//二叉搜索树与双向链表

class Solution {
public:
	void InorderConvert(TreeNode* root, TreeNode*& pre)
	{
		if(root == nullptr)
			return;

		InorderConvert(root->left, pre);
		root->left = pre;
		if(pre != nullptr)
			pre->right = root;
		pre = root;
		InorderConvert(root->right, pre);
	}

    TreeNode* Convert(TreeNode* pRootOfTree) {

		TreeNode* pre = nullptr;
		InorderConvert(pRootOfTree, pre);

		TreeNode* head = pRootOfTree;
		while(head && head->left){head = head->left;}

		return head;
    }
};